package org.example.sword2offer.primary;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: lynn
 * @Descript:  二叉搜索树的第k个结点
 * 给定一棵二叉搜索树，请找出其中的第k小的结点。
 * 例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
 * 核心是 树的中序遍历
 * date: 2021/3/24 23:43
 * version: 1.0
 */public class Q60_KthTreeNode {
     public static void main(String[] args) {
        TreeNode treeNode =  new TreeNode(5);
        treeNode.left =      new TreeNode(3);
        treeNode.right =     new TreeNode(7);
        treeNode.left.left = new TreeNode(2);
        treeNode.left.right= new TreeNode(4);
        treeNode.right.left= new TreeNode(6);
        treeNode.right.right=new TreeNode(8);
         System.out.println(KthNode(treeNode,3));
    }

    private  static TreeNode KthNode(TreeNode pRoot, int k) {
        //利用中序遍历将二叉树转成链表
        if(k==0){ //边界问题，第0小，是不存在
            return null;
        }
        ArrayList<TreeNode> list=new ArrayList<>();
        InTraversal(list,pRoot);
        if (k<=list.size()){
            return list.get(k-1); //第一小代表的是list的index为0
        }
        return null;
    }


    private static void InTraversal(ArrayList<TreeNode> arrayList, TreeNode root){
        if(root == null)
            return;
        InTraversal(arrayList,root.left);
        arrayList.add(root);
        InTraversal(arrayList,root.right);
    }

    private static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
    }
}
